The present invention relates to flash memories and, more particularly, to a method of storing data in multi-bit flash cells.
Flash memory devices have been known for many years. Typically, each cell within a flash memory stores one bit of information. Traditionally, the way to store a bit has been by supporting two states of the cell—one state represents a logical “0” and the other state represents a logical “1”. In a flash memory cell the two states are implemented by having a floating gate above the cell's channel (the area connecting the source and drain elements of the cell's transistor), and having two valid states for the amount of charge stored within this floating gate. Typically, one state is with zero charge in the floating gate and is the initial unwritten state of the cell after being erased (commonly defined to represent the “1” state) and another state is with some amount of negative charge in the floating gate (commonly defined to represent the “0” state). Having negative charge in the gate causes the threshold voltage of the cells transistor (i.e. the voltage that has to be applied to the transistor's control gate in order to cause the transistor to conduct) to increase. Now it is possible to read the stored bit by checking the threshold voltage of the cell: if the threshold voltage is in the higher state then the bit value is “0” and if the threshold voltage is in the lower state then the bit value is “1”. Actually there is no need to accurately read the cell's threshold voltage. All that is needed is to correctly identify in which of the two states the cell is currently located. For that purpose it is enough to make a comparison against a reference voltage value that is in the middle between the two states, and thus to determine if the cell's threshold voltage is below or above this reference value.
FIG. 1A shows graphically how this works. Specifically, FIG. 1A shows the distribution of the threshold voltages of a large population of cells. Because the cells in a flash memory are not exactly identical in their characteristics and behavior (due, for example, to small variations in impurities concentrations or to defects in the silicon structure), applying the same programming operation to all the cells does not cause all of the cells to have exactly the same threshold voltage. (Note that, for historical reasons, writing data to a flash memory is commonly referred to as “programming” the flash memory.) Instead, the threshold voltage is distributed similar to the way shown in FIG. 1A. Cells storing a value of “1” typically have a negative threshold voltage, such that most of the cells have a threshold voltage close to the value shown by the left peak of FIG. 1A, with some smaller numbers of cells having lower or higher threshold voltages. Similarly, cells storing a value of “0” typically have a positive threshold voltage, such that most of the cells have a threshold voltage close to the value shown by the right peak of FIG. 1A, with some smaller numbers of cells having lower or higher threshold voltages.
In recent years a new kind of flash memory has appeared on the market, using a technique conventionally called “Multi Level Cells” or MLC for short. (This nomenclature is misleading, because the previous type of flash cells also have more than one level: they have two levels, as described above. Therefore, the two kinds of flash cells are referred to herein as “Single Bit Cells” (SBC) and “Multi-Bit Cells” (MBC).) The improvement brought by the MBC flash is the storing of two or more bits in each cell. In order for a single cell to store two bits of information the cell must be able to be in one of four different states. As the cell's “state” is represented by its threshold voltage, it is clear that a 2-bit MBC cell should support four different valid ranges for its threshold voltage. FIG. 1B shows the threshold voltage distribution for a typical 2-bit MBC cell. As expected, FIG. 1B has four peaks, each corresponding to one state. As for the SBC case, each state is actually a range and not a single number. When reading the cell's contents, all that must be guaranteed is that the range that the cell's threshold voltage is in is correctly identified. For a prior art example of an MBC flash memory see U.S. Pat. No. 5,434,825 to Harari.
Similarly, in order for a single cell to store three bits of information the cell must be able to be in one of eight different states. So a 3-bit MBC cell should support eight different valid ranges for its threshold voltage. FIG. 1C shows the threshold voltage distribution for a typical 3-bit MBC cell. As expected, FIG. 1C has eight peaks, each corresponding to one state. FIG. 1D shows the threshold voltage distribution for a 4-bit MBC cell, for which sixteen states, represented by sixteen threshold voltage ranges, are required.
When encoding two bits in an MBC cell via the four states, it is common to have the left-most state in FIG. 1B (typically having a negative threshold voltage) represent the case of both bits having a value of “1”. (In the discussion below the following notation is used—the two bits of a cell are called the “lower bit” and the “upper bit”. An explicit value of the bits is written in the form [“upper bit” “lower bit”], with the lower bit value on the right. So the case of the lower bit being “0” and the upper bit being “1” is written as “10”. One must understand that the selection of this terminology and notation is arbitrary, and other names and encodings are possible). Using this notation, the left-most state represents the case of “11”. The other three states are typically assigned by the following order from left to right: “10”, “00”, “01”. One can see an example of an implementation of an MBC NAND flash memory using this encoding in U.S. Pat. No. 6,522,580 to Chen, which patent is incorporated by reference for all purposes as if fully set forth herein. See in particular FIG. 8 of the Chen patent. U.S. Pat. No. 6,643,188 to Tanaka also shows a similar implementation of an MBC NAND flash memory, but see FIG. 7 there for a different assignment of the states to bit encodings: “11”, “10”, “01”, “00”. The Chen encoding is the one illustrated in FIG. 1B.
We extend the above terminology and notation to the cases of more than two bits per cell, as follows. The left-most unwritten state represents “all ones” (“1 . . . 1”), the string “1 . . . 10” represents the case of only the lowest bit of the cell being written to “0”, and the string “01 . . . 1” represents the case of only the most upper bit of the cell being written to “0”.
When reading an MBC cell's content, the range that the cell's threshold voltage is in must be identified correctly; only in this case this cannot always be achieved by comparing to only one reference voltage. Instead, several comparisons may be necessary. For example, in the case illustrated in FIG. 1B, to read the lower bit, the cell's threshold voltage first is compared to a reference comparison voltage V1 and then, depending on the outcome of the comparison, to either a zero reference comparison voltage or a reference comparison voltage V2. Alternatively, the lower bit is read by unconditionally comparing the threshold voltage to both a zero reference voltage and a reference comparison voltage V2, again requiring two comparisons. For more than two bits per cell, even more comparisons might be required.
The bits of a single MBC cell may all belong to the same flash page, or they may be assigned to different pages so that, for example in a 4-bit cell, the lowest bit is in page 0, the next bit is in page 1, the next bit in page 2, and the highest bit is in page 3. (A page is the smallest portion of data that can be separately written in a flash memory). Both methods are in use. While the methods of the present invention are explained here in the context of the “each bit in its own page” approach, these methods also can be applied to the case of all bits residing in the same page.
As was shown above for the 2-bit MBC cell, there is more than one option in how to define the correspondence between the cell's threshold voltage states and the bit encodings they represent. Each such correspondence is equivalent to a specific ordering of the encoded bit patterns along the threshold voltage axis. We saw above that Chen and Tanaka, while disclosing very similar cell designs, used different assignments (and hence different orderings), both equally usable. The object of the current invention is to provide good orderings that are better than other orderings in some sense.
At first glance, one might think that every permutation of ordering all n-bit patterns should be considered for the n-bit MBC cell. The number of permutations of N elements is equal to N! (“N Factorial”). A cell with n bits has 2n different bit patterns, and therefore has 2n! permutations. So this would lead to the 2-bit cell having 4!=24 possible orderings, the 3-bit cell having 8!=40,320 possible orderings, and so on. However, there are restrictions put on the ordering because of the way the flash cells are programmed, and these restrictions reduce the number of orderings that can actually be used.
First, according to the conventions we defined above, the left-most state always corresponds to the “all ones” bit pattern. Second, assuming a design in which each bit resides in a different page, there are restrictions caused by the bits of a cell being written sequentially rather than all at once. One must remember that programming can only increase the threshold voltage of a cell, not reduce it. Reduction of the threshold voltage can only be done when erasing, but erasing can be applied only to large groups of cells (“blocks” in common terminology). Therefore, any ordering of the bit patterns that requires the threshold voltage to decrease when writing a bit to “0” cannot be used. Consider for example a 2-bit MBC cell. Suppose we selected the following order from left to right—“11”, “00”, “10”, “01”. Assume we first wrote the lower bit to “0”, so the cell was brought to the “10” state. Now we want to write the upper bit to “0”. This requires changing the threshold downward, from the state representing “10” to the state representing “00”, but as we noted above, this is impossible to do in typical flash memories. Therefore we should select our ordering of bit patterns in a way that for every legal sequence of bit programming operations, it will never be required to reduce the threshold voltage. An ordering that satisfies these two restrictions is called herein a “valid” ordering. Similarly, an assignment of bit patterns to cell's states that results in a valid ordering is called herein a “valid” assignment.
It is common, in MBC flash memories that assign a cell's bits to different pages, to have a lower bit in a lower-numbered page and to require the user to write the pages in sequential order so that a lower-numbered page is written before a higher-numbered page. We use this practice in the explanations here, but one must understand that the methods of the present invention are equally applicable to other practices of assigning bits to pages and of ordering the writing of pages.
FIG. 2 shows a graphical representation of the restrictions applicable to the ordering of bit patterns in a 2-bit MBC cell. Each bit pattern is shown by its binary representation within a circle, and by its decimal representation outside the circle. Both numerical representations are equivalent, but it is more convenient to use the binary representation for understanding the ordering restrictions, and to use the decimal representation for talking about a certain pattern. An arrow connecting two circles in FIG. 2 means that the state from which the arrow originates must precede the state to which the arrow points.
One can see in FIG. 2 that, as expected, “11” must be the first state. This is seen from the fact this state must precede all other states. Also, “10” must preceded “00”, as shown above. Because of the simplicity of the 2-bit case, it is easy to realize there are only three orderings that satisfy all restrictions:
a. 11, 10, 00, 01 (this is what Chen used)
b. 11, 10, 01, 00 (this is what Tanaka used)
c. 11, 01, 10, 00
FIG. 3 shows the corresponding graphical representation for the case of 3-bit MBC cells, and FIG. 4 shows the corresponding graphical representation for the case of 4-bit MBC cells. Both cases are much more complex than the 2-bit case and allow many more valid orderings.
Let us find out how many legal orderings we have in each case. Consider first the 2-bit case (FIG. 2). As “11” always comes first, we ignore it and consider the equivalent question of how many options we have to put the other three patterns in the right-most three states, while satisfying the restrictions shown in FIG. 2. As “10” and “00” have a strict mandatory order between them, we start by selecting two positions out of the three for putting those two pattern. We designate the number of combinations of n elements taken k at a time as C(n,k), which is equal to (n!)/((n−k)!)/(k!). In this case, k=2 and n=3, and the number of ways to put “10” and “00” in place is 3!/1!/2!=3. The last pattern (“01”) must now be put in the only position left, so we are left with three legal orderings, as we already saw above.
Now let us move to the less trivial 3-bit cell (FIG. 3). We notice that after writing the lowest bit of a 3-bit cell, the other 2 bits (still unwritten) represent the same problem of ordering as a 2-bit cell. This can be seen in FIG. 3 by noticing that the “branch” containing {6,4,0,2} has exactly the same structure as the whole of FIG. 2. But we already know this problem has exactly three different solutions. So let us start the construction of an ordering by selecting positions for the four members of the {6,4,0,2} branch out of the seven available positions (recall that the all-ones pattern always has its left-most reserved position). There are C(7,4) ways of doing this. Each such way has three valid internal orderings of the branch members, so in total we have C(7,4)×3 ways of assigning these four patterns. Now for each such selection, we choose two of the three still unassigned positions for representing the {5,1} branch members. This can be done in C(3,2)=3 ways. The last pattern (3) must go into the only position left. The total product is C(7,4)×3×3=315 valid orderings for a 3-bit MBC cell.
We can make the calculation similarly for a 4-bit MBC cell (FIG. 4). The positions for the eight members of the {14,12,10,6,8,4,2,0} branch can be selected in C(15,8) ways, each one to be multiplied by the 315 possible internal orderings we found above for the 3-bit case. Then we multiply again by 315, which is the number of arrangements we have for putting the remaining seven states into the remaining seven positions. The end result is C(15,8)×315×315=638,512,875. The number of valid orderings of yet larger numbers of bits is enormous.
The Appendices list 3-bit and 4-bit orderings along with analyses of these orderings, as described below. Appendix A lists all 315 3-bit orderings. Appendices B, C, D and E are partial lists of the 4-bit orderings.
The large number of possible bit orderings for MBC cells of more than 2 bits brings up the question which is the best one to use. U.S. Pat. No. 6,046,935 to Takeuchi proposes one method of constructing a bit patterns ordering for MBC cells. FIGS. 86A to 86C of Takeuchi apply the method to 3-bit cells. FIGS. 88A to 88D of Takeuchi apply the method to 4-bit cells. FIGS. 90A to 90E of Takeuchi show how to apply the method to the general M-bit case. However, as will be explained below, the method proposed by Takeuchi results in an ordering that is not optimal.
There is thus a widely recognized need for, and it would be highly advantageous to have, an optimal method of ordering the bits in an MBC cell.